package leetcode;

import java.util.Arrays;

public class NextPermutation {

    public static void main(String[] args) {
        NextPermutation n = new NextPermutation();
//        int arr[] = new int[]{1, 1, 5, 2};
//        int arr[] = new int[]{5,4,7,5,3,2};
        int arr[] = new int[]{1, 3, 2};
        n.nextPermutation(arr);
        Arrays.stream(arr).forEach(System.out::print);
        System.out.println();
    }

    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]){
            i --;
        }
        if(i >= 0){
            // 找到比i 大的那个较大的值
            int j = nums.length - 1;
            while(j >= 0 && nums[i] >= nums[j]){
                j --;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }


    private void swap(int[] nums, int i, int i1) {
        int temp = nums[i];
        nums[i] = nums[i1];
        nums[i1] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

}
